// Pike's Structural Regular Expression* as generalized string matching
//combinators.
//  * http://doc.cat-v.org/bell_labs/structural_regexps/
//
// There are four combinators: X, Y, G, and V.
// The X and Y combinators take a substr.Finder; the G and V combinators take a
//substr.Matcher. The result is itself a substr.Finder that can be fed to the
//G and V combinators.
//
// X is the extract combinator. It extracts all substrings that match its finder
//
// Y is the complement of X. It extracts all substrings that do *not* match its
//finder.
//
// G is the grep combinator. It keeps all substrings that match.
//
// V is the complement of G. It drops all substrings that match.
//
// These combinators chain. They create a finder that performs each operation
//in the chain left to right. A chain is specified like so:
//
//	X(aFinder).V(aMatcher).Y(anotherFinder)
//
// The above creates a finder that splits its string into the substrings defined
//by 'aFinder'. Then each of those substrings is dropped if 'aMatcher' matches
//them. Finally, any remaining substrings are divided further by excising the
//portions returned by 'anotherFinder'.
//
// A more concrete example, taken from http://code.google.com/p/sregex/ but
//avoiding regular expressions when possible:
//	import . "shims" //MustCompile is the shims wrapper of regexp.MustCompile
//	func b(s string) []byte { return []byte(s) } //just to lessen some noise
//	s := []byte("Atom-Powered Robots Run Amok")
//	
//	X( MustCompile("A...") ).Find(s, -1).Strings()
//	==> ["Atom" "Amok"]
//	
//	X( MustCompile("A...") ).X( Suffix( b("m") ) ).Find(s, -1).Strings()
//	==> ["Atom"]
//	
//	Y( Sep( b(" ") ) ).Find(s, -1).Strings()
//	==> ["Atom-Powered" "Robots" "Run" "Amok"]
//	
//	Y( HasAny(" -") ).Find(s, -1).Strings()
//	==> ["Atom" "Powered" "Robots" "Run" "Amok"]
//	
//	Y( Sep( b(" ") ) ).X( MustCompile("R.") ).Find(s, -1).Strings()
//	==> ["Ro" "Ru"]
//	
//	Y( HasAny(" -") ).V( Prefix( b("R") ) ).Find(s, -1).Strings()
//	==> ["Atom" "Powered" "Amok"]
//	
//	Y( HasAny(" -") ).V( Prefix( b("R") ) ).G( Has( b("om") ) ).Find(s, -1).Strings()
//	==> ["Atom"]
package combinators

import "substr"
import "substr/shims"

type pat interface {
	next() pat
	set(pat)
}

type common struct {
	n pat
}

func (c *common) next() pat { return c.n }
func (c *common) set(p pat) { c.n = p }

type mpat struct {
	*common
	m substr.Matcher
}

type fpat struct {
	*common
	f substr.Finder
}

type M struct {
	fst, lst pat
}

func (m *M) add(p pat) *M {
	if m.fst != nil {
		m.lst.set(p)
	} else {
		m.fst = p
	}
	m.lst = p
	return m
}

type oppositeMatcher struct {
	o substr.Matcher
}
func opposite(m substr.Matcher) substr.Matcher { return &oppositeMatcher{m} }
func (o *oppositeMatcher) Match(s []byte) bool { return !o.o.Match(s) }

func X(p substr.Finder) *M  { return (&M{}).X(p) }
func Y(p substr.Finder) *M  { return (&M{}).Y(p) }
func G(p substr.Matcher) *M { return (&M{}).G(p) }
func V(p substr.Matcher) *M { return (&M{}).V(p) }

func (m *M) X(p substr.Finder) *M { return m.add(&fpat{f: p}) }
func (m *M) Y(p substr.Finder) *M { return m.X(shims.Invert(p)) }

func (m *M) G(p substr.Matcher) *M { return m.add(&mpat{m: p}) }
func (m *M) V(p substr.Matcher) *M { return m.G(opposite(p)) }

func (m *M) Find(s []byte, n int) *substr.S {
	ret := substr.New(s, n)
	ret.Push(0, -1)
	for p := m.fst; p != nil; p = p.next() {
		switch t := p.(type) {
		case fpat:
			ret.RefineAll(t.f)
		case mpat:
			ret.Keep(t.m)
		}
		if len(ret.Subs) == 0 {
			return ret
		}
	}
	ret.Trunc(n)
	return ret
}
